/*
题目: 股票价格跨度
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

https://leetcode.cn/problems/online-stock-span
 */
public class StockSpanner {
    private static class Pair {
        int idx;   // 序号
        int price; // 股票价格
        public Pair(int idx, int price) {
            this.idx = idx;
            this.price = price;
        }
    }
    Stack<Pair> stk = null;
    int curIdx = 0; // 记录序号

    public StockSpanner() {
        // 维持一个单调栈 (严格减)
        stk = new Stack<> ();
        stk.push(new Pair(0, Integer.MAX_VALUE)); // 入栈一个初始值
    }

    public int next(int price) {
        curIdx ++;
        while (stk.size() > 0 && stk.peek().price <= price) {
            stk.pop();
        }
        int ret = curIdx - stk.peek().idx;
        stk.push(new Pair(curIdx, price));
        return ret;
    }
}
